The invention relates generally to routing packets in a packet-based network, and more particularly to a method and system for updating forwarding tables that are maintained by network routers.
An internetwork such as a transmission control protocol/Internet protocol (TCP/IP) based intranet or the Internet consists of many interconnected routers. The internetwork has a network topology that must be mapped out, so that the interconnected routers can properly forward packets to other network nodes. Information concerning the topology of networks is stored by routers in forwarding tables and the forwarding tables are consulted by the respective routers each time packets are forwarded.
As the topology of networks change, routers communicate the topology changes to each others. The communicated changes are then incorporated into the forwarding table of each individual router. While updating a single entry in a forwarding table of a router does not present significant difficulties, in many cases the entire forwarding table must be updated. During the time that is required to update a forwarding table, inconsistencies in the table may develop and packets may be incorrectly forwarded because of the table inconsistencies. In order to ensure that a forwarding table is free of inconsistencies before packets are forwarded, it is best to forward packets only after the forwarding table has been completely updated. Although it is best to completely update the forwarding table before forwarding packets, as the rate of packets arriving at a router increases, the time available for updating the forwarding table decreases. As a result, packets must either be forwarded according to a forwarding table that has not been completely updated, or delayed until the forwarding table can be completely updated.
FIG. 1 represents a conventional forwarding table lookup engine 12 and forwarding table memory 14 that is used in an IP-based router to forward packets. When a packet enters the lookup engine, the destination IP address within the packet header is utilized to lookup a next hop address in the forwarding table. In order to properly reflect the current topology of the network, the forwarding table of the router is periodically updated with new route entries. A relatively long period of time is required to update a large portion of the forwarding table, and while the update is in progress, some portions of the forwarding table may not be consistent with the intended forwarding logic. As stated above, during the periods of inconsistency with the intended forwarding logic, it is possible that some packets will be incorrectly forwarded. In order to minimize periods of inconsistency within forwarding tables, it is desirable to update the forwarding tables as fast as possible during periods when no packets are arriving at the router.
One technique for increasing the speed of forwarding table updates involves equipping routers with faster central processing units (CPUs). Although faster CPUs may provide some performance benefits, when network traffic is heavy, faster CPUs are still not be able to complete large forwarding table updates during breaks between packets. As a result, packets must be forwarded utilizing an outdated or potentially inconsistent forwarding table, or packets must be delayed until the forwarding table update is complete, neither of which are desirable outcomes.
Another technique for increasing the speed of forwarding table updates involves making a working copy of a forwarding table before any updates have been made to the forwarding table. Updates are then made to the working copy of the forwarding table while the original forwarding table is utilized to forward packets. Once the working copy has been completely updated, the updated working copy is written over the original forwarding table in order to replace the original forwarding table with the updated working copy. Although this technique may speed up the update process, writing the working copy of the forwarding table over the original copy of the forwarding table takes a significant period of time. During periods of heavy network traffic, writing large forwarding table updates over the original forwarding table may require incoming packets to be forwarded according to an inconsistent forwarding table, or delayed until the forwarding table update is complete.
In view of the need to continuously update forwarding tables in routers and the need to avoid inconsistencies in forwarding tables, what is needed is a system and a method that allow a forwarding table to be updated at speeds provided by conventional CPUs, while eliminating inconsistencies in the forwarding tables that are being utilized to forward packets.
A system and a method for managing forwarding table lookups and updates involve maintaining a first forwarding table in a first memory and a second forwarding table in a second memory, and then utilizing the first forwarding table to forward packets while the second forwarding table is updated with current route entries. The second forwarding table is updated in the background and therefore conventional CPU speeds do not cause performance problems. Once the second forwarding table is completely updated, a forwarding table pointer is switched and the second forwarding table is utilized to forward packets while the first forwarding table is updated. Because the second forwarding table has been completely updated in the background, switching the forwarding table pointer causes newly arriving packets to be forwarded according to a forwarding table that is free of inconsistencies.
In a preferred embodiment, the system includes a lookup engine, a forwarding table pointer, two distinct blocks of forwarding table memory, and an update engine. The lookup engine receives incoming packets and looks at the packet headers to determine the destination of the incoming packets. After the destination of an incoming packet is identified, the lookup engine accesses one of the two forwarding tables to determine the best route (next hop) for the packet, based on the ultimate destination of the packet. Once the best route for the present packet is identified, the packet is forwarded to a switch fabric that is contained within the router.
The two distinct blocks of forwarding table memory allow for the simultaneous storage of two different forwarding tables. That is, the first forwarding table memory stores a first version of a forwarding table, and the second forwarding table memory stores a second version of a forwarding table. Typically, one version of the forwarding table is an updated version of the other forwarding table, although this is not critical. In a preferred embodiment, the two forwarding table memories have identical structure, so that the two forwarding table memories are interchangeable with each other.
The forwarding table pointer identifies which forwarding table memory is active. The active forwarding table memory stores the forwarding table that is accessed by the lookup engine to forward packets. When there are only two possible memories, a one-bit register can be used to identify either of the two forwarding table memories.
The forwarding table update engine coordinates the updates of the two forwarding tables that are stored in the respective forwarding table memories. The preferred forwarding table update engine utilizes conventional techniques to update the forwarding tables and is supported by a standard speed CPU.
In operation, the forwarding table pointer may identify the first forwarding table memory as the active forwarding table memory. The active forwarding table memory stores the forwarding table that is currently being utilized by the lookup engine to route incoming packets. The forwarding table memory that is not identified by the forwarding table pointer is not utilized by the lookup engine to route incoming packets, and is referred to as a secondary forwarding table memory.
While the first forwarding table is being accessed by the lookup engine to forward packets, the second forwarding table, which is stored within the second forwarding table memory, can be updated in the background by the update engine in order to reflect the current topology of the network. While the second forwarding table is being updated, it is not accessed by the lookup engine to forward packets, and as a result a potentially inconsistent forwarding table is not utilized to forward packets.
Once the second forwarding table has been adequately updated, the forwarding table pointer can be quickly switched, causing the second forwarding table memory to be accessed by the lookup engine instead of the first forwarding table memory. In a preferred embodiment, the switching between forwarding table memories occurs in approximately one clock cycle, providing a nearly instantaneous switch between forwarding table memories. As a result of the rapid switch between forwarding table memories, newly arriving packets are always forwarded according to consistent forwarding logic, even when network traffic is heavy.
Although the system for managing forwarding table lookups requires at least two distinct forwarding table memories, it should be appreciated that a system with more than two forwarding table memories can be implemented. For example, a system for managing forwarding table lookups may include four forwarding table memories that are each capable of storing unique forwarding table information. When four forwarding memories are present, the forwarding table pointer is able to identify one of the four forwarding table memories as the active forwarding table memory. The active forwarding table is accessed by the lookup engine to forward packets while the three secondary forwarding tables are available for updating.
An advantage of utilizing at least two forwarding table memories is that forwarding tables containing inconsistent route logic are not utilized to forward packets. Another advantage is that updates of the secondary forwarding table(s) can be performed in the background, relieving the burden on the CPU to perform extremely high-speed table updates.